package com.ch1;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Arrays;

/**
 * 采用外部排序 基于磁盘的多路归并排序
 * @author Linxiaozhi
 *
 */
public class BitSort4 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		if (args.length < 1) {
			System.out.println("usage: java -Xms2M -Xmx2M com.ch1.BitSort4 d:\\input.txt d:\\output.txt");
			return;
		}

		BitSort4 client = new BitSort4();
		long l1 = System.currentTimeMillis();

		client.fun(args[0], args[1]);

		long l2 = System.currentTimeMillis();
		System.out.println("time:" + (l2 - l1));

	}

	public final static int SIZE = 10000000; //总大小
	public final static int TIMES = 80; //次数
	public final static int UNIT = SIZE / TIMES;

	int[] heap = new int[TIMES + 1]; //堆
	int[] indexs = new int[TIMES + 1]; //索引
	boolean[] isNulls = new boolean[TIMES];
	//int[] nums = new int[TIMES];

	void fixUp(int k) {
		int j = 0;
		while ((j = k >> 1) > 0) {
			if (heap[k] >= heap[j])
				break;
			int temp = heap[j];
			heap[j] = heap[k];
			heap[k] = temp;

			temp = indexs[j];
			indexs[j] = indexs[k];
			indexs[k] = temp;

			k = j;
		}
	}

	void fixDown(int k) {
		int size = TIMES;
		int j = 0;
		while ((j = k << 1) <= size && j > 0) {
			if (j + 1 <= size && heap[j + 1] <= heap[j])
				j++;
			if (heap[k] <= heap[j])
				break;
			int temp = heap[j];
			heap[j] = heap[k];
			heap[k] = temp;

			temp = indexs[j];
			indexs[j] = indexs[k];
			indexs[k] = temp;

			k = j;
		}
	}

	void fixDown(int k, int size) {
		int j = 0;
		while ((j = k << 1) <= size && j > 0) {
			if (j + 1 <= size && heap[j + 1] <= heap[j])
				j++;
			if (heap[k] <= heap[j])
				break;
			int temp = heap[j];
			heap[j] = heap[k];
			heap[k] = temp;

			temp = indexs[j];
			indexs[j] = indexs[k];
			indexs[k] = temp;

			k = j;
		}
	}

	void add(int index, int val) {
		indexs[1] = index;
		heap[1] = val;
		fixDown(1);
	}

	int getMin() {
		return heap[1];
	}

	int getWhich() {
		return indexs[1];
	}

	void fun(String inputName, String outputName) {
		try {

			PrintWriter[] pws = new PrintWriter[TIMES];
			for (int i = 0; i < TIMES; i++) {
				pws[i] = new PrintWriter("temp\\temp" + i + ".txt");
			}

			BufferedReader br = new BufferedReader(new FileReader(inputName));
			String s = "";
			int index = 0;
			while ((s = br.readLine()) != null) {
				int in = Integer.parseInt(s);
				PrintWriter pwt = pws[index % TIMES];
				pwt.println(in);
				pwt.flush();
				index++;
			}

			br.close();

			for (int i = 0; i < TIMES; i++) {
				pws[i].close();
			}

			for (int i = 0; i < TIMES; i++) {
				BufferedReader brt = new BufferedReader(new FileReader("temp\\temp" + i + ".txt"));
				index = 0;
				int[] arr = new int[UNIT];
				while ((s = brt.readLine()) != null) {
					int in = Integer.parseInt(s);
					arr[index++] = in;
				}
				arr = Arrays.copyOf(arr, index);
				Arrays.sort(arr);
				PrintWriter pwt = new PrintWriter("temp\\temptemp" + i + ".txt");
				int size = arr.length;
				for (int j = 0; j < size; j++) {
					pwt.println(arr[j]);
				}
				brt.close();
				pwt.close();
				new File("temp\\temp" + i + ".txt").delete();
				new File("temp\\temptemp" + i + ".txt").renameTo(new File("temp\\temp" + i + ".txt"));
			}

			//System.out.println("--------------------------");

			PrintWriter pw = new PrintWriter(outputName);

			//建堆
			BufferedReader[] brs = new BufferedReader[TIMES];
			for (int i = 0; i < TIMES; i++) {
				brs[i] = new BufferedReader(new FileReader("temp\\temp" + i + ".txt"));
				int in = Integer.parseInt(brs[i].readLine());
				heap[i + 1] = in;
				indexs[i + 1] = i;
			}
			for (int i = 2; i <= TIMES; i++) {
				fixUp(i);
			}
			String st = "";
			boolean flag = false;
			while (true) {
				int in = getMin();
				pw.println(in);
				int which = getWhich();
				int orgin = which;

				st = null;
				if (!isNulls[which]) {
					st = brs[which].readLine();
					//nums[which]++;
					if (st == null) {
						//System.out.println(which + ":" + nums[which]);
						isNulls[which] = true;
					}
				}
				while (isNulls[which]) {
					which++;
					which = which % TIMES;

					if (which == orgin) {
						//System.out.println("orgin:" + orgin);
						flag = true;
						break;
					}
					if (!isNulls[which]) {
						st = brs[which].readLine();
						//nums[which]++;
						if (st == null) {
							//System.out.println(which + ":" + nums[which]);
							isNulls[which] = true;
						}
					}
				}

				if (flag)
					break;

				int val = Integer.parseInt(st);
				add(which, val);
			}

			//将堆中剩余的元素按顺序输出
			int size = TIMES;
			heap[1] = heap[size];
			size--;
			fixDown(1, size);
			//System.out.println(Arrays.toString(heap));
			while (size > 0) {
				int in = getMin();
				pw.println(in);

				heap[1] = heap[size];
				size--;
				fixDown(1, size);
			}

			pw.flush();
			pw.close();
			//System.out.println(Arrays.toString(nums));
			//System.out.println(Arrays.toString(isNulls));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		}

	}

}
